package com.leetcode.hot100;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: com.leetcode.hot100
 * @Author: lei
 * @CreateTime: 2024-03-24  21:15
 * @Description: 关键在于使用二维数组寻找对应的关系
 * @Version: 1.0
 */
public class 零钱兑换02 {
    public static void main(String[] args) {
        int amount = 10;
        int[] coins = {10};
        System.out.println(change(amount, coins));
    }

    public static int change(int amount, int[] coins) {
        int[][] ints = new int[2][amount + 1];
        for (int i = 0; i < coins.length; i++) {
            ints[(i + 1) & 1][0] = 1;
            for (int j = 1; j < amount + 1; j++) {
                if (j < coins[i]) {
                    ints[(i + 1) & 1][j] = ints[i & 1][j];
                } else {
                    int count = j - coins[i];
                    ints[(i + 1) & 1][j] = ints[i & 1][j] + ints[(i + 1) & 1][count];
                }
            }
        }
        return ints[(coins.length) & 1][amount];
    }

}
